﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;



public class Solution226
{
    //递归
    public TreeNode InvertTree2(TreeNode root)
    {
        if (root == null)
        {
            return null;
        }

        TreeNode temp= InvertTree(root.left);
        root.left= InvertTree(root.right);
        root.right = temp; 
        
        
        return root;



    }
    //迭代
    public TreeNode InvertTree(TreeNode root)
    {

        //先序遍历的时候，交换左右孩子

        Queue<TreeNode> list = new Queue<TreeNode>();
        Stack<TreeNode> s = new Stack<TreeNode>();



      



        while (root != null || s.Count > 0)
        {

            while (root != null)
            {
                s.Push(root);
                TreeNode temp = root.left;
                root.left = root.right;
                root.right = temp;

                root = root.left;
            }
            root = s.Pop();
            root = root.right;
        }

        

        return root;

        


    }
}

public class Program226
{
   


}